public class PrimeNumbers {
    // 判断单个数字是否为素数（基础版，后续分析它的性能）
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        // 只检查到平方根，且步长为2（只遍历奇数）
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 用「埃拉托斯特尼筛法」批量找素数（优化版）
    public static void sieveOfEratosthenes(int max) {
        boolean[] isPrime = new boolean[max + 1];
        for (int i = 2; i <= max; i++) {
            isPrime[i] = true; // 初始假设所有数都是素数
        }
        // 从2开始，标记每个素数的倍数为非素数
        for (int i = 2; i * i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // 输出结果（每行5个）
        int count = 0;
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) {
                System.out.print(i + "\t");
                count++;
                if (count % 5 == 0) System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        int range = 20000;

        // ========== 方法1：逐个判断（测试耗时） ==========
        System.out.println("===== 方法1：逐个判断素数 =====");
        long start1 = System.currentTimeMillis();
        int count1 = 0;
        for (int num = 2; num <= range; num++) {
            if (isPrime(num)) {
                System.out.print(num + "\t");
                count1++;
                if (count1 % 5 == 0) System.out.println();
            }
        }
        long end1 = System.currentTimeMillis();
        System.out.println("\n逐个判断总耗时: " + (end1 - start1) + " 毫秒");


        // ========== 方法2：埃拉托斯特尼筛法（测试耗时） ==========
        System.out.println("\n===== 方法2：埃拉托斯特尼筛法 =====");
        long start2 = System.currentTimeMillis();
        sieveOfEratosthenes(range);
        long end2 = System.currentTimeMillis();
        System.out.println("\n筛法总耗时: " + (end2 - start2) + " 毫秒");


        // ========== 性能分析与改进 ==========
        System.out.println("\n--- 性能分析与改进 ---");
        System.out.println("最费时的函数（方法1中）：isPrime（逐个判断素数的函数）");
        System.out.println("原因：对每个数都要循环判断，重复计算多，时间复杂度O(n√n)。");
        System.out.println("改进方法：");
        System.out.println("1. 用「埃拉托斯特尼筛法」（如方法2）：通过“标记倍数”一次性找出所有素数，时间复杂度O(n log log n)，更高效；");
        System.out.println("2. 预处理小素数：若需频繁判断素数，可预先存储小素数表，减少重复计算；");
        System.out.println("3. 多线程优化：把数值范围拆分给多个线程并行计算（适合更大范围，如百万级以上）。");
    }
}